Fingerprinting is a technique that involves uniquely marking each copy of a particular object, and associating each uniquely marked copy with a particular entity to which the copy is distributed. If unauthorized copies of the uniquely marked copy are made, the fingerprint can be traced back to the original entity to which the copy was initially distributed.
As an example, consider a printed map. When a map maker produces a map, they may want to ensure that those individuals to whom the map is distributed do not make unauthorized copies of the map and distribute them to others. One way that the map maker might protect his maps is to introduce a different trivial error, or fingerprint, (e.g. a non-existent street) into each of the copies of the map that are distributed. Each fingerprint is then associated with an individual to whom the map is to be distributed. By associating each different fingerprint with a different individual, if and when unauthorized copies of that individual's copy are uncovered, they can be traced back to the original individual by virtue of the unique fingerprint that the map contains.
One problem with this type of fingerprinting can arise when two or more individuals collude for the purpose of discovering their fingerprints. That is, when two or more individuals get together and compare their maps, they can, given enough time, ascertain their unique fingerprints by simply looking for the differences between their maps. If they can ascertain their fingerprint, they can alter it and therefore possibly avoid detection.
In contemporary times, particularly with the advent of the Internet and electronic distribution, fingerprinting digital data (e.g. software, documents, music, and video) for purposes of detecting or deterring unauthorized copying has become particularly important. As in the above map example, collusion by different individuals in the digital context can pose challenges to the owners and distributors of such digital data. Although progress has been made in the area of digital fingerprinting, further strides are necessary to increase the breadth of protection that is afforded by digital fingerprinting. For example, in one fingerprinting system (the “Boneh-Shaw system” discussed in more detail below), some protection against collusion is provided, but only when the number of colluders is relatively small. Thus, there is a need to increase the protection that is provided by digital fingerprinting to provide detection of colluders even when the number of colluders is large.
Accordingly, this invention arose out of concerns associated with providing improved methods and systems for fingerprinting digital data.